package com.gxc.slidingWindow;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 */
public class FindAnagrams {

    public static void main(String[] args) {
        findAnagrams("baa", "aa");
    }

    public static List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        int[] count = new int[26];
        for (int i = 0; i < p.length(); i++) {
            count[p.charAt(i) - 'a']--;
            count[s.charAt(i) - 'a']++;
        }
        int diff = 0;
        for (int i = 0; i < count.length; i++) {
            if (count[i]!=0) diff++;
        }

        int left = 0, right = p.length();
        List<Integer> list = new ArrayList<>();
        if (diff == 0) list.add(0);
        while (right < s.length()) {
            char add = s.charAt(right);
            char prev = s.charAt(left);
            if (count[prev - 'a'] == 1) {
                diff--;
            } else if (count[prev - 'a'] == 0) {
                diff++;
            }
            count[prev - 'a']--;

            if (count[add - 'a'] == -1) {
                diff--;
            } else if (count[add - 'a'] == 0) {
                diff++;
            }
            count[add - 'a']++;

            if (diff == 0) {
                list.add(left+1);
            }
            left++;
            right++;
        }
        return list;
    }
}
